12.33 An alternative to the 2-d tree is the quad tree. Figure 12.52 shows how a plane is partitioned by a quad tree. Initially we have a region (which is often a square, but need not be). Each region may store one point. If a second point is inserted into a region, then the region is split into four equal-sized quadrants (northeast, southeast, southwest, and northwest). If this places the points in different quadrants (aswhen p2 is inserted), we are done; otherwise, we continue splitting recursively (as is done when p5 is inserted). a. For a given set of N items, does the order of insertion affect the final partition? b. Show the final partition if the same elements that were in the 2-d tree in Figure 12.39 are inserted into the quad tree. - | |
| View Solution | |
| << Back | Next >> |